package com.hxm.demo.test1;

/**
 * description: add a description
 *
 * @author huangxiaoming
 * @version 1.0.0
 * @date 2022/10/26 11:24:14
 */
public class TestCheckInclusion {

    /**
     * 567. 字符串的排列
     *
     * @param args
     */
    public static void main(String[] args) {
        String s1 = "ab", s2 = "eidbaooo";
        System.out.println(checkInclusion(s1, s2));
    }

    /**
     * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
     * <p>
     * 换句话说，s1 的排列之一是 s2 的 子串
     *
     * @param s1
     * @param s2
     * @return
     */
//    public static boolean checkInclusion(String s1, String s2) {
//        int n = s1.length();
//        int m = s2.length();
//        int[] c1 = new int[26];
//        int[] c2 = new int[26];
//        if (n > m) {
//            return false;
//        }
//        for (int i = 0; i < n; i++) {
//            c1[s1.charAt(i) - 'a']++;
//            c2[s2.charAt(i) - 'a']++;
//        }
//
//        if (Arrays.equals(c1, c2)) {
//            return true;
//        }
//
//        for (int i = n; i < m; i++) {
//            c2[s2.charAt(i) - 'a']++;
//            c2[s2.charAt(i - n) - 'a']--;
//            if (Arrays.equals(c1, c2)) {
//                return true;
//            }
//        }
//        return false;
//    }
//    public static boolean checkInclusion(String s1, String s2) {
//        int n = s1.length();
//        int m = s2.length();
//        int[] c = new int[26];
//        int diff = 0;
//        if (n > m) {
//            return false;
//        }
//        for (int i = 0; i < n; i++) {
//            c[s1.charAt(i) - 'a']--;
//            c[s2.charAt(i) - 'a']++;
//        }
//        for (int i : c) {
//            if (i != 0) {
//                diff++;
//            }
//        }
//        if (diff == 0) {
//            return true;
//        }
//        for (int i = n; i < m; i++) {
//            int x = s2.charAt(i) - 'a';
//            int y = s2.charAt(i - n) - 'a';
//            if (x == y) {
//                continue;
//            }
//            if (c[x] == 0) {
//                diff++;
//            }
//            c[x]++;
//            if (c[x] == 0) {
//                diff--;
//            }
//            if (c[y] == 0) {
//                diff++;
//            }
//            c[y]--;
//            if (c[y] == 0) {
//                diff--;
//            }
//            if (diff == 0) {
//                return true;
//            }
//        }
//        return false;
//    }
    public static boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[] c = new int[26];
        if (n > m) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            c[s1.charAt(i) - 'a']--;
        }
        int left = 0;
        for (int right = 0; right < m; right++) {
            int x = s2.charAt(right) - 'a';
            c[x]++;
            while (c[x] > 0) {
                c[s2.charAt(left)-'a']--;
                left++;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}
